import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.*;

public class Test2 {
    void postOrderNor(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            TreeNode prev = null;//方便记录

            if (top.right == null || top.right == prev) {
                System.out.print(top.val + " ");
                stack.pop();
                prev = top;
            } else {
                cur = top.right;
            }
        }
    }
    void inOrderNor(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur. left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");`

            cur = top.right;
        }

    }

    void preOrderNor(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }
    boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
            } else {
                break;
            }
        }

        while (!queue.isEmpty()) {
            TreeNode cur = queue.peek();
            if (cur == null) {
                queue.poll();
            } else {
                return false;
            }
        }

        return true;
    }

    int getHeight (TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

    TreeNode find(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val = val) {
            return root;
        }

        TreeNode ret1 = find(root.left, val);
        if (ret1 != null) {
            return ret1;//不去右边了，因为找到了
        }

        TreeNode ret2 = find(root.right, val);
        if (ret2 != null) {
            return ret2;
        }
        return null;
    }

    int CountLevel(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return CountLevel(root.left, k - 1) + CountLevel(root.right, k - 1);
    }
    public static void main(String[] args) {
        //双端队列
        Deque<Integer> deque1 = new LinkedList<>();//用双向链表实现
        Deque<Integer> deque2 = new ArrayDeque<>();//用循环数组实现
    }
    public static void main1(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        //因为Queue是接口，不能直接实例化
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        System.out.println(queue.peek());
        System.out.println(queue.poll());//出队
        System.out.println(queue);
        System.out.println();
    }
}
